struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    // 思路：一组一组的翻转链表，用greupPre指向上一组的最后一个节点，然后找到当前组的最后一个节点cur，保存下一组的起始节点groupNxt，然后翻转当前组的节点，最后更新groupPre指向当前组的最后一个节点
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode *dummy = new ListNode(0, head);
        ListNode *groupPre = dummy; // 上一组的最后一个节点
        while (true)
        {
            // 1. 找到当前组的最后一个节点
            ListNode *cur = groupPre; // 为什么是groupPre，因为groupPre是上一组的最后一个节点，cur从groupPre开始向后移动k个节点
            int kth = k;
            while (kth > 0 && cur) // cur不为空: 不够k个节点，直接返回。 k>0: 还没找到k个节点
            {
                --kth;
                cur = cur->next;
            }
            if (!cur) // 不够k个，直接返回
                break;
            // 2. 下一组的起始节点
            ListNode *groupNxt = cur->next; // 为什么是cur->next，因为cur是当前组的最后一个节点，需要指向下一组的起始节点
            // 3. 翻转当前组内的上k个节点
            ListNode *pre = groupNxt; // 为什么是groupNxt，因为翻转后第一个节点要指向下一组的起始节点
            cur = groupPre->next;     // 当前组的第一个节点
            ListNode *temp = nullptr; // 临时节点
            while (cur != groupNxt)   // 翻转当前组的节点
            {
                temp = cur->next; // 先保存下一个节点
                cur->next = pre;  // 指向前一个节点
                pre = cur;        // 更新前一个节点
                cur = temp;       // 更新当前节点
            }
            // 一组翻转完成，更新groupPre
            temp = groupPre->next; // 翻转前的第一个节点，翻转后变成了最后一个节点
            groupPre->next = pre;  // groupPre指向翻转后的第一个节点
            groupPre = temp;       // 更新groupPre指向当前组的最后一个节点
        }
        return dummy->next; // 返回新的头节点
    }
};